import java.util.*;

public class MyHeap {
    public int[] elem;
    public int usedSize;

    public MyHeap(){
        this.elem=new int[10];
    }

    public void createHeap(int[] array){

        for(int i=0;i<array.length;i++){
            this.elem[i]=array[i];
            usedSize++;
        }

        for(int p=(usedSize-1-1)/2;p>=0;p--){
            shiftDown(p,usedSize);
        }

    }

    private void shiftDown(int root,int len){//由上至下调整大根堆
        int parent=root;
        int child=parent*2+1;
        //如果有孩子，找到左右孩子的最大值
        while(child<len){
            if(child+1<len&&elem[child+1]>elem[child]){
                child++;
            }
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    public void push(int val){//入队：仍然要保持是大根堆
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //1.放到最后位置
        this.elem[usedSize]=val;
        //2.向上调整
        shiftUp(usedSize);
        //3.数据+1
        usedSize++;
    }

    private void shiftUp(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child=parent;
                parent=(parent-1)/2;
            }else{
                break;
            }
        }
    }

    public void pollHeap(){//出队，保证是大根堆
        if(isEmpty()){
            System.out.println("优先级队列为空！");
            return;
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;//交换最后一个孩子的值与根节点值
        usedSize--;
        shiftDown(0,usedSize);
    }

    public int peekHeap(){//获取堆顶元素
        if(isEmpty()) {
            System.out.println("优先级队列为空！");
            return -1;
        }
        return elem[0];
    }


    public boolean isFull() {
        return usedSize == elem.length;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

}
